Let equation image be the semigroup of all mappings on the natural numbers equation image, and let U and V be subsets of equation image. We write U≼V if there exists a countable subset C of equation image such that U is contained in the subsemigroup generated by V and C. We give several results about the structure of the preorder ≼. In particular, we show that a certain statement about this preorder is equivalent to the Continuum Hypothesis.The preorder ≼ (...) is analogous to one introduced by Bergman and Shelah on subgroups of the symmetric group on equation image. The results in this paper suggest that the preorder on subsemigroups of equation image is much more complicated than that on subgroups of the symmetric group. (shrink)

Let ΩΩ be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of ΩΩ, then we write U≈V if there exists a finite subset F of ΩΩ such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in ΩΩ is the least cardinality of a subset A of ΩΩ such that the union of U and A generates ΩΩ. In this paper (...) we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or in ΩΩ where is the minimum cardinality of a dominating family for . We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in ΩΩ are 0, 1, 2, and .We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 20. (shrink)